
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 第一遍 2/28
     * @param head
     * @return
     */
//    public boolean isPalindrome(ListNode head) {
//        // 快慢指针
//        // 奇数链表的话，slow在中间
//        // 偶数链表的话，slwo在中间+1
//        ListNode slow = head, fast = head;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//        // 上面走完，奇数链，fast有可能没走到null，但是偶数链因为没有限制fast.next.next，所以偶数链走到null
//        if (fast != null) {
//            slow = slow.next;
//        }
//
//        // 反转slow到尾部的链
//        ListNode left = head;
//        // 这里返回的是反转之后的链
//        ListNode right = reverse(slow);
//        // 头尾同时起步
//        while (right != null) {
//            if (left.val != right.val) {
//                return false;
//            }
//            left = left.next;
//            right = right.next;
//        }
//        return true;
//    }
//
//    ListNode reverse(ListNode head) {
//        ListNode pre = null, cur = head;
//        while (cur != null) {
//            ListNode next = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = next;
//        }
//        return pre;
//    }


    /**
     * 第二遍 2/28
     * @param head
     * @return
     */
//    public boolean isPalindrome(ListNode head) {
//        // 快慢指针
//        ListNode slow = head, fast = head;
//        while (fast != null && fast.next != null) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//        if (fast != null) {
//            slow = slow.next;
//        }
//
//        // 反转链表
//        ListNode left = head;
//        ListNode right = reverse(slow);
//        while (right != null) {
//            if (left.val != right.val) {
//                return false;
//            }
//            left = left.next;
//            right = right.next;
//        }
//        return true;
//    }
//
//    ListNode reverse(ListNode head) {
//        ListNode pre = null, cur = head;
//        while (cur != null) {
//            ListNode nxt = cur.next;
//            cur.next = pre;
//            pre = cur;
//            cur = nxt;
//        }
//        return pre;
//    }


    /**
     * 第三遍 3/3
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        // 使用快慢指针，寻找链表中点
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 这时候奇数链表slow为中间，fast在末尾，并未指向null
        // 这时候偶数链表slow为中间，fast指向null
        if (fast != null) {
            slow = slow.next;
        }

        // 反转链表
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
